<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        function TreeNode(val, left, right) {
            this.val = (val === undefined ? 0 : val)
            this.left = (left === undefined ? null : left)
            this.right = (right === undefined ? null : right)
        }
        // 1.层序遍历
        var levelOrder = function (root) {
            let que = []
            let result = []
            if (root) que.push(root)

            while (que.length > 0) {

                let length = que.length
                let level = []
                for (let i = 0; i < length; i++) {
                    let node = que.shift()
                    level.push(node.val)
                    if (node.left) que.push(node.left)
                    if (node.right) que.push(node.right)
                }
                result.push(level)
            }
            return result
        };
        // 2.自下而上，自左而右
        var levelOrder2 = function (root) {
            let que = []
            let result = []
            if (root) que.push(root)

            while (que.length > 0) {
                let length = que.length
                let level = []
                for (let i = 0; i < length; i++) {
                    let node = que.shift()
                    level.unshift(node.val)
                    
                    if (node.right) que.push(node.right)
                    if (node.left) que.push(node.left)
                }
                result.unshift(level)
            }
            return result
        };
        // 3.从右侧观察
        var levelOrder3 = function (root) {
            let que = []
            let result = []
            if (root) que.push(root)
            while (que.length > 0) {
                let length = que.length
                for (let i = 0; i < length; i++) {
                    let node = que.shift()
                    if(i==(length-1)) result.push(node.val) // 每层的最后一个节点
                    if (node.left) que.push(node.left)
                    if (node.right) que.push(node.right)
                    
                }
            }
            return result
        };
        let root = new TreeNode(1)
        root.left = new TreeNode(2)
        root.right = new TreeNode(3)
        root.right.right = new TreeNode(4)
        root.left.right = new TreeNode(5)
        console.log(levelOrder(root))
        console.log(levelOrder2(root))
        console.log(levelOrder3(root))
    </script>
</body>

</html>